package com.jyl.dptask; // 本章属于动态规划练习

/**
 * 爬楼梯
 * @ClassName P70
 * @Author admin
 * @Date 2024/6/15
 */
public class P70 {

    public static void main(String[] args) {
        /*
        n=3
          1+1+1; 1+2 ;2+1
        n=4
          1+1+1+1; 1+1+2; 1+2+1; 2+1+1; 2+2;
         */
        System.out.println(climbStairs(4));
        System.out.println(climbStairsByDP(4));
    }

    protected static int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        return climbStairs(n - 1) + climbStairs(n - 2);
    }

    protected static int climbStairsByDP(int n) {

        int p2 = 1;

        int p1 = 2;

        if (n == 1) {
            return 1;
        }

        if (n == 2) {
            return 2;
        }

        for (int i = 3; i <= n; i++) {
            int result = p2 + p1;
            p2 = p1;
            p1 = result;
        }
        return p1;

    }


}
